%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Short Sectioned Assignment
% LaTeX Template
% Version 1.0 (5/5/12)
%
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% Original author:
% Frits Wenneker (http://www.howtotex.com)
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------

\documentclass[paper=a4, fontsize=11pt]{scrartcl} % A4 paper and 11pt font size

\usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs
\usepackage{fourier} % Use the Adobe Utopia font for the document - comment this line to return to the LaTeX default
\usepackage[english]{babel} % English language/hyphenation
\usepackage{amsmath,amsfonts,amsthm} % Math packages
\usepackage[UTF8]{ctex}
\usepackage{xcolor}
\usepackage{listings}
\usepackage{tikz}
\usepackage{lipsum} % Used for inserting dummy 'Lorem ipsum' text into the template
\usepackage{clrscode}
\usepackage{sectsty} % Allows customizing section commands
\usepackage[framed,numbered,autolinebreaks,useliterate]{mcode}
\usetikzlibrary{graphs}
\usetikzlibrary{shapes.arrows}
\allsectionsfont{\centering \normalfont\scshape} % Make all sections centered, the default font and small caps

\usepackage{fancyhdr} % Custom headers and footers
\pagestyle{fancyplain} % Makes all pages in the document conform to the custom headers and footers
\fancyhead{} % No page header - if you want one, create it in the same way as the footers below
\fancyfoot[L]{} % Empty left footer
\fancyfoot[C]{} % Empty center footer
\fancyfoot[R]{\thepage} % Page numbering for right footer
\renewcommand{\headrulewidth}{0pt} % Remove header underlines
\renewcommand{\footrulewidth}{0pt} % Remove footer underlines
\setlength{\headheight}{13.6pt} % Customize the height of the header

\numberwithin{equation}{section} % Number equations within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)
\numberwithin{figure}{section} % Number figures within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)
\numberwithin{table}{section} % Number tables within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)

\setlength\parindent{0pt} % Removes all indentation from paragraphs - comment this line for an assignment with lots of text

%----------------------------------------------------------------------------------------
%	TITLE SECTION
%----------------------------------------------------------------------------------------

\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height

\title{
\normalfont \normalsize
\textsc{中国科学院大学}\ \textsc{计算机与控制学院} \\ [25pt] % Your university, school and/or department name(s)
\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule
\huge 算法设计与分析第一次作业 \\ % The assignment title
\horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule
}

\author{黎吉国} % Your name

\date{\normalsize\today} % Today's date or a custom date

\begin{document}

\maketitle % Print the title
Notice:\\\\
\begin{enumerate}
\item Please submit your answer in hard copy AND submit a digital version to UCAS website http://sep.ucas.ac.cn.
\item Hard copy should be submitted before 9  am. September 30 and digital version should be submitted before 12 pm. September 30.
\item You can choose \textbf{three} from problems 1-7, and choose \textbf{two} from problems 8-11.
\item For problems 1-7, you should do at least the following things:
\begin{enumerate}
 \item Describe your algorithm in natural language \textbf{AND} pseudo-code;
 \item Draw a ``subproblem reduction graph", where nodes represent subproblems, and edges describe the ``reduction relationship" between them for every problem you choose in problems 1-7;
 \item Prove the correctness of your algorithm;
 \item Analyse the complexity of your algorithm.
\end{enumerate}
\item For problems 8-11, you should implement your algorithm in C/C++/Java/Python with good comments.
\end{enumerate}
%----------------------------------------------------------------------------------------
%	PROBLEM 1
%----------------------------------------------------------------------------------------
\newpage
\section{Answer to the 1st}

\paragraph{} You are interested in analyzing some hard-to-obtain data from two separate databases. Each database contains $n$ numerical values, so there are $2n$ values total and you may assume that no two values are the same. You'd like to determine the median of this set of $2n$ values, which we will define here to be the $n^{th}$ smallest value.

\paragraph{}However, the only way you can access these values is through $queries$ to the databases. In a single query, you can specify a value $k$ to one of the two databases, and the chosen database will return the $k^{th}$ smallest value that it contains. Since queries are expensive, you would like to compute the median using as few queries as possible.

\paragraph{}Give an algorithm that finds the median value using at most $O(\log n)$ queries.

\textbf{题目分析：}对于这个问题，我们最容易想到的是使用归并的方法将两个有序序列合并成一个有序序列，合并$n$个后停止，就得到了中位数，但是这个算法的复杂度是$O(n)$，它做了一些我们不需要的事情，比如对前$n$个数的排序，我们不需要知道他们的排序，只需要知道他们比中位数小。这里我们研究中位数在这两个序列中的特点。\\
假设两个序列分别为$A,B$，他们各有$n$个元素：\\
\begin{tikzpicture}
  %\foreach \x in {1}
  %\foreach \y in {1,2,3,4,5,6,7}
  %{
  %  \draw (\x,\y) +(-.5,-.5) rectangle ++(.5,.5);
  %  \draw (\x,\y) node{A(\y)};
  %}
  \filldraw[fill=green!20,draw=green!50!black] (0,0) rectangle (1,1);
  \draw (0.5,0.5) node{A(1)};
  \filldraw[fill=green!20,draw=green!50!black] (1,0) rectangle (2,1);
  \draw (1.5,0.5) node{A(2)};
  \filldraw[fill=green!20,draw=green!50!black] (2,0) rectangle (3,1);
  \draw (2.5,0.5) node{...};
  \filldraw[fill=red!50,draw=green!50!black] (3,0) rectangle (4,1);
  \draw (3.5,0.5) node{A(k)};
  \filldraw[fill=green!20,draw=green!50!black] (4,0) rectangle (5,1);
  \draw (4.5,0.5) node{...};
  \filldraw[fill=green!80,draw=green!50!black] (5,0) rectangle (6,1);
  \draw (5.5,0.5) node{A(n/2)};
  \filldraw[fill=green!20,draw=green!50!black] (6,0) rectangle (7,1);
  \draw (6.5,0.5) node{...};
  \filldraw[fill=green!20,draw=green!50!black] (7,0) rectangle (8,1);
  \draw (7.5,0.5) node{...};
  \filldraw[fill=green!20,draw=green!50!black] (8,0) rectangle (9,1);
  \draw (8.5,0.5) node{...};
  \filldraw[fill=green!20,draw=green!50!black] (9,0) rectangle (10,1);
  \draw (9.5,0.5) node{A(n-1)};
  \filldraw[fill=green!20,draw=green!50!black] (10,0) rectangle (11,1);
  \draw (10.5,0.5) node{A(n)};

  \filldraw[fill=green!20,draw=green!50!black] (0,2) rectangle (1,3);
  \draw (0.5,2.5) node{B(1)};
  \filldraw[fill=green!20,draw=green!50!black] (1,2) rectangle (2,3);
  \draw (1.5,2.5) node{B(2)};
  \filldraw[fill=green!20,draw=green!50!black] (2,2) rectangle (3,3);
  \draw (2.5,2.5) node{...};
  \filldraw[fill=green!20,draw=green!50!black] (3,2) rectangle (4,3);
  \draw (3.5,2.5) node{...};
  \filldraw[fill=green!20,draw=green!50!black] (4,2) rectangle (5,3);
  \draw (4.5,2.5) node{...};
  \filldraw[fill=green!80,draw=green!50!black] (5,2) rectangle (6,3);
  \draw (5.5,2.5) node{B(n/2)};
  \filldraw[fill=green!20,draw=green!50!black] (6,2) rectangle (7,3);
  \draw (6.5,2.5) node{...};
  \filldraw[fill=red!20,draw=green!50!black] (7,2) rectangle (8,3);
  \draw (7.5,2.5) node{B(m)};
  \filldraw[fill=green!20,draw=green!50!black] (8,2) rectangle (9,3);
  \draw (8.5,2.5) node{...};
  \filldraw[fill=green!20,draw=green!50!black] (9,2) rectangle (10,3);
  \draw (9.5,2.5) node{B(n-1)};
  \filldraw[fill=green!20,draw=green!50!black] (10,2) rectangle (11,3);
  \draw (10.5,2.5) node{B(n)};


%\filldraw[fill=green!20,draw=green!50!black] (0,0) rectangle (1,1);

\end{tikzpicture}\\
如上图所示，我们将两个序列的$n/2$处都标出来，假设$A(k)$是两个序列的中位数，而是满足$B(m)<A(k)andB(m+1)>A(k)$的值，易知$m+k=n$.\\
此处容易得到$B(n/2)<B(m)<A(k)<A(n/2)$，这个结论反过来也成立，即\\
$B(n/2)<A(n/2)\to$ $A(k)$在$A$序列的前半段，$B(m)$在$B$序列的后半段。\\
这里我们在这样的特定情况下，想办法缩小问题的规模：我们从$n/2$处将双序列分成四个序列，挑选出包含$A(k)$和$B(m)$的两个小序列。\\
\begin{tikzpicture}
  %\foreach \x in {1}
  %\foreach \y in {1,2,3,4,5,6,7}
  %{
  %  \draw (\x,\y) +(-.5,-.5) rectangle ++(.5,.5);
  %  \draw (\x,\y) node{A(\y)};
  %}
  \filldraw[fill=green!20,draw=green!50!black] (0,0) rectangle (1,1);
  \draw (0.5,0.5) node{A(1)};
  \filldraw[fill=green!20,draw=green!50!black] (1,0) rectangle (2,1);
  \draw (1.5,0.5) node{A(2)};
  \filldraw[fill=green!20,draw=green!50!black] (2,0) rectangle (3,1);
  \draw (2.5,0.5) node{...};
  \filldraw[fill=red!50,draw=green!50!black] (3,0) rectangle (4,1);
  \draw (3.5,0.5) node{A(k)};
  \filldraw[fill=green!20,draw=green!50!black] (4,0) rectangle (5,1);
  \draw (4.5,0.5) node{...};
  \filldraw[fill=green!80,draw=green!50!black] (5,0) rectangle (6,1);
  \draw (5.5,0.5) node{A(n/2)};

  \filldraw[fill=green!20,draw=green!50!black] (6,2) rectangle (7,3);
  \draw (6.5,2.5) node{...};
  \filldraw[fill=red!20,draw=green!50!black] (7,2) rectangle (8,3);
  \draw (7.5,2.5) node{B(m)};
  \filldraw[fill=green!20,draw=green!50!black] (8,2) rectangle (9,3);
  \draw (8.5,2.5) node{...};
  \filldraw[fill=green!20,draw=green!50!black] (9,2) rectangle (10,3);
  \draw (9.5,2.5) node{B(n-1)};
  \filldraw[fill=green!20,draw=green!50!black] (10,2) rectangle (11,3);
  \draw (10.5,2.5) node{B(n)};
%\filldraw[fill=green!20,draw=green!50!black] (0,0) rectangle (1,1);

\end{tikzpicture}\\
如上图所示，如果感觉$A(k)$也是新的双序列的中位数，我们证明一下：\\
比$A(k)$小的数有多少：$m-n/2+k=n/2$\\
说明猜测是正确的，这样，我们成功把问题缩减了。当双序列都只有一个数的时候，较小的一个就是我们要的解。\\
下面整理上面的算法：\\
(a)伪代码
\begin{codebox}
  \Procname{$\proc{Mid}(A[a,a+k],B[b,b+k])$}
  \li \If $k=0$
  \li \Then
  \li     \Return $\min(A[a],B[b])$
  \li \Else \If $A[a+k/2]<B[b+k/2]$
  \li       \Then
  \li         \Return $\proc{Mid}(A[a,a+k/2],B[b+k/2,b+k])$
  \li       \Else
  \li         \Return $\proc{Mid}(A[a+k/2,a+k],B[b,b+k/2])$
          \End
     \End
\end{codebox}
(b)归约图\\
\begin{tikzpicture}
  [sibling distance=65mm, level distance=35mm,
  edge from parent/.style={draw,dashed,thick}]
\node{Mid(A[1,n],B[1,n])}
 child{
  node{Mid(A[1,n/2],B[n/2,n])}
    child{
      node{...}
    }
    child{
      node{...}
    }
  edge from parent
  node{A(n/2)>B(n/2)}
  }
 child{
  node{Mid(A[n/2,n],B[1,n/2])}
  child{
    node{...}
  }
  child{
    node{...}
  }
  edge from parent
  node{A(n/2)<B(n/2)}
 };
\end{tikzpicture}\\
需要注意的是这里我们并不是将一个问题分为两个子问题，而是通过一次比较就将问题的规模减半。所以解决问题只需要$\log n$次比较和一次子问题求解。所以其时间复杂度是$O(\log n)$.
(c)证明算法的正确性\\
这里使用数学归纳法证明。\\
这里其实是前面算法分析的逆过程。\\
(1)问题规模为1时，显然成立。\\
(2)假设问题规模为$n/2$时成立，证明其规模为$n$时也成立。\\
\begin{tikzpicture}
  %\foreach \x in {1}
  %\foreach \y in {1,2,3,4,5,6,7}
  %{
  %  \draw (\x,\y) +(-.5,-.5) rectangle ++(.5,.5);
  %  \draw (\x,\y) node{A(\y)};
  %}
  \filldraw[fill=green!20,draw=green!50!black] (0,0) rectangle (1,1);
  \draw (0.5,0.5) node{A(1)};
  \filldraw[fill=green!20,draw=green!50!black] (1,0) rectangle (2,1);
  \draw (1.5,0.5) node{A(2)};
  \filldraw[fill=green!20,draw=green!50!black] (2,0) rectangle (3,1);
  \draw (2.5,0.5) node{...};
  \filldraw[fill=red!50,draw=green!50!black] (3,0) rectangle (4,1);
  \draw (3.5,0.5) node{A(k)};
  \filldraw[fill=green!20,draw=green!50!black] (4,0) rectangle (5,1);
  \draw (4.5,0.5) node{...};
  \filldraw[fill=green!80,draw=green!50!black] (5,0) rectangle (6,1);
  \draw (5.5,0.5) node{A(n/2)};

  \filldraw[fill=green!20,draw=green!50!black] (0,2) rectangle (1,3);
  \draw (0.5,2.5) node{B(1)};
  \filldraw[fill=green!20,draw=green!50!black] (1,2) rectangle (2,3);
  \draw (1.5,2.5) node{B(2)};
  \filldraw[fill=green!20,draw=green!50!black] (2,2) rectangle (3,3);
  \draw (2.5,2.5) node{...};
  \filldraw[fill=red!20,draw=green!50!black] (3,2) rectangle (4,3);
  \draw (3.5,2.5) node{B(m)};
  \filldraw[fill=green!20,draw=green!50!black] (4,2) rectangle (5,3);
  \draw (4.5,2.5) node{...};
  \filldraw[fill=green!20,draw=green!50!black] (5,2) rectangle (6,3);
  \draw (5.5,2.5) node{B(n/2)};
%\filldraw[fill=green!20,draw=green!50!black] (0,0) rectangle (1,1);
\end{tikzpicture}\\
\begin{tikzpicture}[every node/.style={single arrow, draw=none, rotate=270}]
\node [fill=blue!50, single arrow head indent=1ex] at (1.5,0) {规模翻倍};
\end{tikzpicture}\\
\begin{tikzpicture}
  \filldraw[fill=green!20,draw=green!50!black] (0,0) rectangle (1,1);
  \draw (0.5,0.5) node{A(1)};
  \filldraw[fill=green!20,draw=green!50!black] (1,0) rectangle (2,1);
  \draw (1.5,0.5) node{A(2)};
  \filldraw[fill=green!20,draw=green!50!black] (2,0) rectangle (3,1);
  \draw (2.5,0.5) node{...};
  \filldraw[fill=red!50,draw=green!50!black] (3,0) rectangle (4,1);
  \draw (3.5,0.5) node{A(k)};
  \filldraw[fill=green!20,draw=green!50!black] (4,0) rectangle (5,1);
  \draw (4.5,0.5) node{...};
  \filldraw[fill=green!80,draw=green!50!black] (5,0) rectangle (6,1);
  \draw (5.5,0.5) node{A(n/2)};
  \filldraw[fill=green!50,draw=green!50!black] (6,0) rectangle (12,1);
  \draw (8.5,0.5) node{$A_{add}$};

  \filldraw[fill=green!50,draw=green!50!black] (0,2) rectangle (6,3);
  \draw (3.5,2.5) node{$B_{add}$};
  \filldraw[fill=green!20,draw=green!50!black] (6,2) rectangle (7,3);
  \draw (6.5,2.5) node{B(1)};
  \filldraw[fill=green!20,draw=green!50!black] (7,2) rectangle (8,3);
  \draw (7.5,2.5) node{B(2)};
  \filldraw[fill=green!20,draw=green!50!black] (8,2) rectangle (9,3);
  \draw (8.5,2.5) node{...};
  \filldraw[fill=red!20,draw=green!50!black] (9,2) rectangle (10,3);
  \draw (9.5,2.5) node{B(m)};
  \filldraw[fill=green!20,draw=green!50!black] (10,2) rectangle (11,3);
  \draw (10.5,2.5) node{..};
  \filldraw[fill=green!20,draw=green!50!black] (11,2) rectangle (12,3);
  \draw (11.5,2.5) node{B(n/2)};
%\filldraw[fill=green!20,draw=green!50!black] (0,0) rectangle (1,1);
\end{tikzpicture}\\
如上图所示，$A(k)$是序列$A,B$的中位数，$B(m)<A(k)<B(m+1),m+k=n/2$，并且该序列有一个重要特点：$A(n/2)>B(1)$或者$A(1)<B(n/2)$，这里我们假设$A(n/2)>B(1)$，我们加入两个$n/2$的序列$A_{add},B_{add}$，有$B_{add}<B(1)<B(m)<A(k)$，说明$A(k)$是之后的序列的中位数。
(3)由(1)(2)知该算法对任意规模问题适用。\\

(d)由问题分析中可知，该算法的时间复杂度是$O(\log n)$.下面用递推来证明。
对于每一步的分解有:\\
$T(n)=T(n/2)+O(1)$\\
则$T(n)=O(\log n)$\\
\newpage
\section{Answer to the 2ed}

\paragraph{}Find the $k^{th}$ largest element in an unsorted array. Note that it is the $k$th largest element in the sorted order, not the $k^{th}$ distinct element.

\paragraph{}INPUT: An unsorted array $A$ and $k$.

\paragraph{}OUTPUT: The $k^{th}$ largest element in the unsorted array $A$.

\textbf{问题分析：}这个问题可以使用排序来解决，快速排序的时间复杂度为$O(n\log n)$，但是它做了很多我们不需要的工作，比如$K^{th}$之前和之后的数据的顺序。比如我们使用冒泡排序，只对前$k$个元素排序，这样我们的算法复杂度是$O(kn)$，但是还是做了很多不必要的工作，我们应该直奔主题，直接去寻找第$k$大的元素。
假如拿到了一个元素，如何知道是就是$k^{th}$需要将它与所有其余元素作比较，将其余元素分为两个集合，比他大$A_e$的和比他小$A_l$的（注意这里没有排序），如果恰好$A_e$有$k$个元素，那么这就是要找的答案，如果很不幸，$A_e$中的元素多于$k$个，那说明$k^{th}$在$A_e$中，再对$A_e$做同样的事情即可，这一遍比较虽然没有找到我们想到的答案，但是我们缩减了问题的规模，平均来看，每次比较将问题规模缩减一倍，
当问题规模变为1时，问题将被解决。
下面整理以上的问题分析：\\
(a)伪代码
\begin{codebox}
  \Procname{$\proc{kth-largest}(A,k)$}
  \li   $n \gets A->size()$
  \li   $pivot \gets rand(n)$
  \li   \For $i \gets 1$ \To $n$
  \li \Comment $A_g,A_l$ are tow queue
  \li   \Do \If $A(i)>pivot$
  \li       \Then $A_g->push(A(i))$
  \li       \Else $A_l->push(A(i))$
            \End
        \End
  \li   \If $A_g->size()=k-1$
  \li   \Then \Return $pivot$
  \li   \Else \If $A_g->size()>k-1$
  \li         \Then \Return $\proc{kth-largest}(A_g,k)$
  \li         \Else \Return $\proc{kth-largest}(A_l,k-1-A_g->size())$
              \End
        \End
\end{codebox}
(b)归约图\\
\begin{tikzpicture}
  [sibling distance=65mm, level distance=30mm,
  edge from parent/.style={draw,dashed,thick}]
\node{$kth-largest(A,k)$}
 child{
  node{$kth-largest(A_e,k)$}
    child{
      node{...}
    }
    child{
      node{...}
    }
  edge from parent
  node{$A_g.size<k-1$}
  }
 child{
  node{$kth-largest(A_l,k-1-A_g.size())$}
  child{
    node{...}
  }
  child{
    node{...}
  }
  edge from parent
  node{$A_g.size<k-1$}
 };
\end{tikzpicture}\\
这里每一个分支都是“或”。\\
(c)证明算法的正确性。\\
这里主要证明两点，一个是递推过程的正确性，一个是递推后的问题是可解的。\\
(1)递推过程：需要证明\\
  (i)$A_g.size()>k-1$时，$kth-largest(A_g,k)$是$kth-largest(A,k)$的解\\
  (ii)$A_g.size()<k-1$时，$kth-largest(A_l,k-1-A_g.size())$是$kth-largest(A,k)$的解\\
  (iii)$A_g.size()=k-1$时，$pivot$是$kth-largest(A,k)$的解\\
  \textbf{证：}\\
  (iii)显然成立.\\
  对(i)，$A_g.size()>k-1$时，$k-1$个比$k^{th}$大的数都在$A_g$中，所以$kth-largest(A_g,k)$是$kth-largest(A,k)$的解。\\
  对(ii),$A_g.size()<k-1$时,知$A_g>pivot>k^{th}$， 所以$A_l$中有$k-1-A_g.size()$个比$k^{th}$大的数，所以$kth-largest(A_l,k-1-A_g.size())$是$kth-largest(A,k)$的解。\\
  得证。\\
(d)复杂度分析\\
在最坏情况下，该算法的复杂度是$O(kn)$，这种情况下每次的主元都是最大值。\\
在最好的情况下，算法的复杂度是$O(1)$，第一次就找到$k^{th}$。\\
期望的时间复杂度是$O(n)$(此处查阅相关资料，暂时还不会证明)。\\
\newpage
\section{Answer to 3th}

\paragraph{}Consider an $n$-node complete binary tree $T$, where $n=2^d-1$ for some $d$. Each node $v$ of $T$ is labeled with a real number $x_v$. You may assume that the real numbers labeling the nodes are all distinct. A node $v$ of $T$ is a $local\ minimum$ if the label $x_v$ is less than the label $x_w$ for all nodes $w$ that are joined to $v$ by an edge.

\paragraph{}You are given such a complete binary tree $T$, but the labeling is only specified in the following $implicit$ way: for each node $v$, you can determine the value $x_v$ by $probing$ the node $v$. Show how to find a local minimum of $T$ using only $O(\log n)\ probes$ to the nodes of $T$.

\textbf{问题分析：}
由于问题的搜索空间是$n$，而要求的时间复杂度是$n\log n$，不可能做全局搜索，只能牺牲一部分的精度做局部搜索。先考察根节点和叶子节点，叶子节点只有一个连接，只要它的父节点比他大，他就是满足要求的值，这里我们暂称这种情况为情况一。
下面我们使用“爬山法”来进行局部搜索，如果定义启发函数为$min(N,N.l_child,N.r_child)$，则我们将沿着一条下降的路走下去，最坏的情况是走到一条叶子节点，出现上述的“情况一”，依然能够得到一个解。下面描述算法过程。\\
(a)伪代码\\
\begin{codebox}
\li  \Procname{$\proc{LocalMin}(N)$} //N is the root of the complete binary tree
\li  \If $N.lchild \ne NULL$
\li    \Then $Lvalue=N.lchild.value$
\li    \Else $Lvalue=\infty$
       \End
\li \If $N.rchild \ne NULL$
\li    \Then $Rvalue=N.rchild.value$
\li    \Else $Rvalue=\infty$
       \End
\li $Nvalue=N.value$
\li $minValue=\min (Nvalue,Lvalue,Rvalue)$
\li \If $minValue = Nvalue$
\li   \Then \Return $N$
\li  \Else \If $minValue = Lvalue$
\li        \Then \Return $LocalMin(N.rchild)$
\li        \Else \Return $LocalMin(N.rchild)$
           \End
     \End
\end{codebox}

(b)归约图\\
\begin{tikzpicture}
[level distance=10mm,
every node/.style={fill=red!60,circle,inner sep=1pt},
level 1/.style={sibling distance=20mm,nodes={fill=red!45}},
level 2/.style={sibling distance=10mm,nodes={fill=red!30}},
level 3/.style={sibling distance=5mm,nodes={fill=red!25}}]
\node (a) at (0,0){31}
child {node {30}
  child {
    node {25}
    child {node {5}}
    child {node {4}}
    }
  child {
    node {21}
    child {node {9}}
    child {node {1}}
    }
  }
child[blue] {
  node {20}
  child[blue] {
    node {15}
    child[blue] {node {1}}
    child[black] {node {2}}
  }
  child[black] {
    node {18}
    child {node{3}}
    child {node{4}}
  }
};
\node (b) at (4,0) {$T(15)$}
child[grow=down]{
  node{$T(7)$}
  child[grow=down]{
    node{$T(3)$}
    child[grow=down]{
      node{$T(1)$}
    }
  }
};
\end{tikzpicture}\\
(d)复杂度分析\\
$T(n)=T(n/2)+O(1) \to T(n)=O(\log n)$

\newpage
\section{answer to 8th}

\paragraph{}Recall the problem of finding the number of inversions. As in the course, we are given a sequence of $n$ numbers $a_1,\cdots,a_n$, which we assume are all distinct, and we difine an inversion to be a pair $i<j$ such that $a_i>a_j$.

\paragraph{}We motivated the problem of counting inversions as a good measure of how different two orderings are. However, one might feel that this measure is too sensitive. Let's call a pair a $significant\ inversion$ if $i<j$ and $a_i>3a_j$. Given an $O(n\log n)$ algorithm to count the number of significant inversions between two orderings.

(1)我们先实现$Sort-and-Count$算法，如下：
\lstset{language=Matlab}%代码语言使用的是matlab
\lstset{breaklines}%自动将长的代码行换行排版
\lstset{extendedchars=false}%解决代码跨页时，章节标题，页眉等汉字不显示的问题
\begin{lstlisting}[frame=single]
function [RC,A_sorted]=find_inv_pair(A)
%find_inv_pair.m
%A is a matrix of Nx1,RC is the num of inversion pair
[RC,A_sorted]=sort_and_count(A);
end
function [RC,A_sorted]=sort_and_count(A)
A_size=size(A);
% if A is not a matrix of Nx1, reshape it
if A_size(2)>1
    A=reshape(A,[],1);
    A_size=size(A);
end
%if A is a number, return it
if A_size(1)==1
    A_sorted=A;
    RC=uint16(0);
    return;
end
%devide it and then conquer
L_size=A_size(1)/2;
A_left=A(1:L_size,1);
A_right=A(L_size+1:A_size,1);
%recursion,
[RC_left,A_left]=sort_and_count(A_left);
[RC_right,A_right]=sort_and_count(A_right);
%combine
[C,A_sorted]=merge_and_count(A_left,A_right);

RC=RC_left+RC_right+C;
%A_sorted=A_sorted
end
function [RC,A_sorted]=merge_and_count(L,R)
L_size=size(L);
R_size=size(R);
%give a integar
k=1;
RC=uint16(k)-1;
index1=uint16(k),index2=uint16(k),k=uint16(k);
A_sorted=zeros(L_size(1)+R_size(1),1);
for k=1:L_size(1)+R_size(1)
    if index1>L_size(1)
         A_sorted(k,1)=R(index2,1);
        index2=index2+1;
    else if index2>R_size(1)
            A_sorted(k,1)=L(index1,1);
            index1=index1+1;
            RC = RC + L_size(1)-index1+1;
        else if L(index1,1)>R(index2,1)
                A_sorted(k,1)=R(index2,1);
                index2=index2+1;
                RC = RC + L_size(1)-index1+1;
            else
                A_sorted(k,1)=L(index1,1);
                index1=index1+1;
            end
        end
    end
end
end
\end{lstlisting}
测试结果如下：
\begin{lstlisting}
>> A=[2;5;3;1;7;4;6;8];
>> [RC,A_sorted]=find_inv_pair(A);
>> RC

RC =

      7
>> A=[5;2;3;1;7;4;6;8];
>> [RC,A_sorted]=find_inv_pair(A);
>> RC

RC =

    8
\end{lstlisting}
(2)这里不适合使用快速排序，原因如下：\\
我们分解到最后的子问题是单个数，解决两个数的排序问题不涉及具体算法，两个算法都可以覆盖两个元素的排序问题。\\
迭代过程中，我们得到的是两个排好序的序列，此时使用快速排序则没有利用两个序列有序的信息，相当于重新打乱重新排序，必然增加时间复杂度。所以这里不适合使用快速排序。

\newpage
\section{answer to 9th}

\paragraph{}Implement the algorithm for the closest pair problem in your favourite language.

\paragraph{} INPUT: $n$ points in a plane.

\paragraph{} OUTPUT: The pair with the least Euclidean distance.

使用matlab实现$divide\ and\ conquer$解决该问题的程序如下：
\begin{lstlisting}[frame=single]
  function [distance,point]=least_E_distance(Points);
  %Points={x1,x2,x3...;y1,y2,y3...}, it is unsorted
  P_size=size(Points);
  if P_size(2)==2
      x_diff=Points(1,1)-Points(1,2);
      y_diff=Points(2,1)-Points(2,2);
      distance=sqrt(x_diff^2+y_diff^2);
      point=[0,0;0,0];
      return;
  else if P_size(2)<2
          distance=+inf;
          point=[0,0;0,0];
          return;
      end
  end
  if P_size(1) ~= 2
      error('Points is not a 2xN matrix');
  end
  %divide
  x_mid=Points(1,1)/2+Points(1,2)/2;

  k=uint16(1);
  k_left=uint16(1);
  k_right=uint16(1);
  for k=1:P_size(2)
      if Points(1,k)<x_mid
          P_left(:,k_left)=Points(:,k);
          k_left = k_left+1;
      else
          P_right(:,k_right)=Points(:,k);
          k_right=k_right+1;
      end
  end
  [l_distance,l_point]=least_E_distance(P_left);
  [r_distance,r_point]=least_E_distance(P_right);
  l_r_min=min(l_distance,r_distance);
  [c_distance,c_point]=combine_left_right(P_left,P_right,l_r_min,x_mid);
  distance=min(l_r_min,c_distance);
  if distance == l_distance
      point=l_point;
  else if distance== r_distance
          point=r_point;
      else
          point=c_point;
      end
  end
  end

  function [distance,points]=combine_left_right(P_left,P_right,distance_min,x_mid);

  x_min=x_mid-distance_min;
  x_max=x_mid+distance_min;
  distance=+inf;
  points=[0,0;0,0];

  l_size=size(P_left);
  r_size=size(P_right);
  j=uint16(1);
  k=uint16(1);
  %select the point where x_min<x<x_max
  for j=1:l_size(2)
      if P_left(1,j)>=x_min && P_left(1,j)<=x_max
          l_selected(:,k)=P_left(:,j);
          k=k+1;
      end
  end
  k=uint16(1);
  for j=1:r_size(2)
      if P_right(1,j)>=x_min && P_right(1,j)<=x_max
          r_selected(:,k)=P_right(:,j);
          k=k+1;
      end
  end
  l_size=size(l_selected);
  r_size=size(r_selected);
  min_distance=+inf;
  tmp_distance=0;
  for j=1:l_size(2)
      for k=1:r_size(2)
          tmp_distance=get_distance(l_selected(:,j), r_selected(:,k));
          if(tmp_distance<min_distance)
              points(:,1)=l_selected(:,j);
              points(:,2)=r_selected(:,j);
              min_distance=tmp_distance;
          end
      end
  end
  end

  function distance=get_distance(A,B);
  x_diff=A(1,1)-B(1,1);
  y_diff=A(2,1)-B(2,1);
  distance=sqrt(x_diff^2+y_diff^2);
  end
\end{lstlisting}
测试结果如下：
\begin{lstlisting}[frame=single]
>> P=[0,1,2,3,4,5,6;0,1,2,3,2,1,0];
>> least_E_distance(P)
ans =

    1.4142
>> P=[0,1,2,3,4,5,6;0,1,2,3,2,1,0.5];
>> least_E_distance(P)
ans =

   1.1180
\end{lstlisting}

%----------------------------------------------------------------------------------------

\end{document}
